package tiruvury.InterviewPrep.DataStructures;

import java.util.PriorityQueue;

public class MyHeap
{
	public static int FindMedian(int num, PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap)
	{
		int median = 0;
		int maxHeapRoot = (maxHeap.size() > 0) ? maxHeap.peek().intValue() : Integer.MAX_VALUE;
		int minHeapRoot = (minHeap.size() > 0) ? minHeap.peek().intValue() : Integer.MIN_VALUE;

		if (num <= maxHeapRoot)
		{
			// num belongs in the maxHeap
			if (maxHeap.size() > minHeap.size())
			{
				minHeap.offer(maxHeap.poll());
			}
			maxHeap.offer(num);
		}
		else
		{
			// num belongs in the minHeap
			if (minHeap.size() > maxHeap.size())
			{
				maxHeap.offer(minHeap.poll());
			}
			minHeap.offer(num);
		}

		if (maxHeap.size() > minHeap.size())
		{
			median = maxHeap.peek().intValue();
		}
		else if (maxHeap.size() < minHeap.size())
		{
			median = minHeap.peek().intValue();
		}
		else
		{
			median = (maxHeap.peek().intValue() + minHeap.peek().intValue()) / 2;
		}

		return median;
	}
}
